/* 
 * Candy
 * n children, each child is assigned a rating value
 * each child must have at least one candy
 * children with a higher rating get more candies than their neighbors
 */

#include "../../func.h"

int candy(vector<int> &ratings)
{
    const int n = ratings.size();
    vector<int> increment(n);

    for (int i = 1, inc = 1; i < n; ++i)
    {
        if (ratings[i] > ratings[i - 1])
            increment[i] = max(inc++, increment[i]);
        else
            inc = 1;
    }

    for (int i = n - 2, inc = 1; i >= 0; --i)
    {
        if (ratings[i] > ratings[i + 1])
            increment[i] = max(inc++, increment[i]);
        else
            inc = 1;
    }

    return accumulate(&increment[0], &increment[n], n);
}

int candy2(vector<int> &ratings)
{
    vector<int> f(ratings.size());
    int sum = 0;
    for (int i = 0; i < ratings.size(); ++i)
        sum += solve(ratings, f, i);
    return sum;
}
int solve(vector<int> &ratings, vector<int> &f, int i)
{
    if (0 == f[i])
    {
        f[i] = 1;
        if (i > 0 && ratings[i] > ratings[i - 1])
            f[i] = max(f[i], solve(ratings, f, i - 1) + 1);
        if (i < ratings.size() && ratings[i] > ratings[i + 1])
            f[i] = max(f[i], solve(ratings, f, i + 1) + 1);
    }
    return f[i];
}